package algocasts;

import java.util.Arrays;

public class P89_ShortestUnsortedContinuousSubArray {
    public int findUnsortedSubarray_Sorting(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        int i = 0, j = sorted.length - 1;
        while (i < nums.length && sorted[i] == nums[i]) i++;
        while (j >= 0 && sorted[j] == nums[j]) j--;
        return Math.max(j - i + 1, 0);
    }

    public int findUnsortedSubarray_TwoPass(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int i = 0, j = n - 1;
        while (i < n - 1 && nums[i] <= nums[i + 1]) ++i;
        while (j > 0 && nums[j] >= nums[j - 1]) --j;
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int k = i; k <= j; k++) {
            max = Math.max(max, nums[k]);
            min = Math.min(min, nums[k]);
        }
        while (i >= 0 && min < nums[i]) --i;
        while (j < n && max > nums[j]) ++j;
        return Math.max(j - i - 1, 0);
    }

    public int findUnsortedSubarray_OnePass(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int i = 0, j = -1, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int k = 0; k < n; ++k) {
            max = Math.max(max, nums[k]);
            if (nums[k] != max) j = k;
            int p = n - 1 - k;
            min = Math.min(min, nums[p]);
            if (min != nums[p]) i = p;
        }
        return j - i + 1;
    }
}
